#!/usr/bin/python
# vim: set fileencoding=utf-8 :
# Linear Combination class.

from hexaPosInt import posInt

class linearCombination :
    """Linear Combination Class
    """
    def __init__(self, v) :
        """ Instantiate a LinearCombination as v = [a0, a1, ..., ak] so, v = a0 * x0 +  a1 * x1 + ... + ak * xk.
        """
        self.val = v

    def __call__(self, x) :
        """ Returns a Linear Combination of vectors v and x. So, v0 * x0 + v1 * x1 + ... + vK * xk.
        """
        r = 0
        for s in len(self.val) :
            r = r + self.val[s] * x[s]
        return r

    def __get__(self, o, t):
        """ Get
        """
        return linearCombination(self.val)

    def __set__(self, o, v):
        """ Set
        """
        self.val = v

    def __getattribute__(self, key):
        """x.__getattribute__('name') <==> x.name
        Emulate type_getattro() in Objects/typeobject.c
        """
        v = object.__getattribute__(self, key)
        if hasattr(v, '__get__'):
            return v.__get__(None, self)
        return v

    def gcd (self) :
        """ Return the Greatest Common Divisor from a Linear Combination by the Euclidean Method.
        """
        a = self.val[0]
        for i in range(len(self.val) - 1) :
            b = self.val[i + 1]
            while b != 0 :
                t = b
                b = a % t
                a = t
        return a

    def egcd (self) :
        """The extended Euclidean algorithm is an extension to the Euclidean algorithm. Besides finding the greatest common divisor of integers 'a' and 'b', as the Euclidean algorithm does, it also finds integers 'x' and 'y' (one of which is typically negative) that satisfy Bézout's identity: a * x + b * y = gcd (a,b).
        """
        x = posInt(0)
        lastx = posInt(1)
        y = posInt(1)
        lasty = posInt(0)
        a = self.val[0]
        b = self.val[1]
        while b != 0 :
            quotient = a // b
            (a, b) = (b, a % b)
            (x, lastx) = (lastx - x * quotient, x)
            (y, lasty) = (lasty - y * quotient, y)
        return [lastx, lasty]

